package cn.fcraft;

import cn.fcraft.utils.Fraction;

import java.util.Arrays;
import java.util.Scanner;

/*
Sample1:
4 5
1 0 0 3 4
0 2 -1 -1 0
0 3 0 -2 1
2 -1 4 0 5
Sample2:
3 4
1 2 -7 -4
2 1 1 13
3 9 -36 -33
*/

public class Solver {
    private static Fraction[][] save_matrix;

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int m,n;//m行n列
        m = s.nextInt();
        n = s.nextInt();
        if (n != m + 1) {
            System.out.println("目前仅可解有唯一解的方程组");
            return;
        }
        Fraction[][] matrix= new Fraction[m][n];
        int zero_count = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                matrix[i][j]= new Fraction(s.nextInt());
                if (j == 0 && matrix[i][j].son == 0) zero_count++;//记录首列的0个数,方便后面排序后翻转
            }
        }

        int row = 0;//row是正在处理的列
        while (row <= n-2) {//n-2是因为最后一列是常数
            /*通过冒泡排序法对row行及其之后的行进行排序*/
            for (int i = row; i < m - 1 - row; i++) {//i从row开始是因为前面已经排好了几列
                for (int j = row; j < m - 1 - i - row; j++) {
                    if (matrix[j][row].getAbsValue() > matrix[j + 1][row].getAbsValue()) {
                        Fraction[] temp = matrix[j];
                        matrix[j] = matrix[j + 1];
                        matrix[j + 1] = temp;
                    }
                }
            }
            output(matrix,"排序:"+row);

            /*将row行及其之后的行进行旋转,目的是将0放到正确的位置*/
            //copyOfRange复制的是从from(包含)到to(不包含),注意下标从0开始
            Fraction[][] copy_matrix = Arrays.copyOfRange(matrix,row,m);//将需要操作的行复制到新数组里
            Fraction[][] temp_matrix = new Fraction[m-row][n];//定义一个临时数组用于储存旋转的
            for (int i = 0; i < temp_matrix.length; i++) {
                temp_matrix[(temp_matrix.length + i - zero_count) % temp_matrix.length] = copy_matrix[i];//旋转
            }
            System.arraycopy(temp_matrix,0,matrix,row,temp_matrix.length);//旋转好的放回原数组

            output(matrix,"旋转:"+row);

            /*将row行的首项上下方的值变为0*/
            Fraction temp_f;
            for (int i = 0; i < m; i++) {
                if (matrix[i][row].son != 0 && i != row) {//非0且非自己所在行
                    temp_f = Fraction.divide(matrix[i][row],matrix[row][row]);//temp_f现在为第i行对第row行的倍数
                    //对第i行进行处理
                    for (int j = 0; j < n; j++) {
                        matrix[i][j].subtract(Fraction.multiply(matrix[row][j],temp_f));//对第i行j列的数字进行处理
                    }
                }
            }

            output(matrix,"处理首项上下:"+row);

            /*取下一列即row+1列的0数量*/
            zero_count = 0;
            if (row <= n - 3) {
                for (int i = row + 1; i < m - (row + 1); i++) {
                    if (matrix[i][row + 1].son == 0) {
                        zero_count++;
                    }
                }
            }
            row++;
        }

        output(matrix,"初步结果:");

        StringBuilder result = new StringBuilder();
        for (int i = 0; i < m; i++) {//化到最简
            Fraction temp_f = matrix[i][i];
            matrix[i][n - 1].divide(temp_f);//常数
            matrix[i][i].son = 1;
            matrix[i][i].mom = 1;
            result.append((matrix[i][n - 1].son >= 0) ? "+" : "")
                    .append(matrix[i][n - 1].son)
                    .append((matrix[i][n - 1].mom == 1) ? "" : "/" + matrix[i][n - 1].mom)
                    .append((i==m-1)?"":",");
        }
        output(matrix,"最终结果:");


        System.out.println("原方程组的解是("+result+")");
    }

    //格式化输出矩阵
    private static void output(Fraction[][] matrix, String hint) {
        //if (Arrays.deepEquals(matrix, save_matrix)) return;
        System.out.println(hint);
        StringBuilder string_matrix = new StringBuilder();
        for (int i = 0; i < matrix.length; i++) {
            if (matrix.length == 1) string_matrix.append("[");
            else if (i == 0) string_matrix.append("┌");
            else if (i == matrix.length - 1) string_matrix.append("└");
            else string_matrix.append("├");
            for (int j = 0; j < matrix[i].length; j++) {
                string_matrix.append((matrix[i][j].son >= 0) ? "+" : "").append(matrix[i][j].son).append((matrix[i][j].mom == 1) ? "" : "/" + matrix[i][j].mom);
                if (j != matrix[i].length - 1) string_matrix.append(" ");
            }
            if (matrix.length == 1) string_matrix.append("]");
            else if (i == 0) string_matrix.append("┐");
            else if (i == matrix.length - 1) string_matrix.append("┘");
            else string_matrix.append("┤");
            string_matrix.append("\n");
        }
        System.out.print(string_matrix);
        //save_matrix = Arrays.copyOfRange(matrix,matrix.length,matrix[0].length);

    }
    private static void output(Fraction[][] matrix) {
        output(matrix,"");
    }
}
